package code;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class Code18 {
	public void dfs(int step,int n,int start,int[] nums,int left,List<Integer> list,List<List<Integer>> res){
		if(step==4 || left<0){
			if(left==0)
				res.add(new ArrayList<Integer>(list));
			return ;
		}
		for(int i=start;i<n;i++){
			if(i>0 && nums[i-1]==nums[i])
				continue;
			if(left>=nums[i]){
				list.add(nums[i]);
				dfs(step+1,n,i+1,nums,left-nums[i],list,res);
				list.remove(list.size()-1);
			}
		}
	}
    public List<List<Integer>> fourSum(int[] nums, int target) {
    	List<List<Integer>> res=new ArrayList<List<Integer>>();
    	Arrays.sort(nums);
    	int n=nums.length;
    	dfs(0,n,0,nums,target,new ArrayList<Integer>(),res);
        return res;
    }
    public static void main(String[] args){
    	int[] nums={1,0,-1,0,-2,2};
    	new Code18().fourSum(nums, 0);
    }
}
